/*
 * @Author: szx
 * @Date: 2022-03-24 14:26:03
 * @LastEditTime: 2022-03-24 14:42:07
 * @Description:
 * @FilePath: \leetcode\剑指offer\36\36.js
 */
function Node(val, left, right) {
    this.val = val;
    this.left = left;
    this.right = right;
}

/**
 * @param {Node} root
 * @return {Node}
 */
var treeToDoublyList = function (root) {
    if (!root) return null;
    let head = root;
    while (head.left) head = head.left;
    let prev = null;
    const dfs = (root) => {
        if (!root) return;
        dfs(root.left);
        if (prev) {
            prev.right = root;
            root.left = prev;
        }
        prev = root;
        dfs(root.right);
    };
    dfs(root);
    prev.right = head;
    head.left = prev;
    return head;
};
